A
不妨设 。
令 ,且 。
则 。
从而 ,一共只有 种情况,讨论一下即可。
Code
#include <cstdio>
int main() {
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
printf("%d\n", (n / 2 + n / 3) * 2 + n);
}
}
B
容易发现排列是有周期性的,只需要处理 的方格表,循环输出即可。
Code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 505;
char mp[N][N];
int T, n, k, r, c;
void solve() {
scanf("%d%d%d%d", &n, &k, &r, &c);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
mp[i][j] = '.';
}
r = (r - 1) % k + 1;
c = (c - 1) % k + 1;
for (int i = 1; i <= k; i++) {
mp[r--][c++] = 'X';
if (r == 0) r = k;
if (c == k + 1) c = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
putchar(mp[(i - 1) % k + 1][(j - 1) % k + 1]);
puts("");
}
}
int main() {
scanf("%d", &T);
while (T--) solve();
}
C
后面我都不会做了
首先必须要求 ,否则必然不可行。
由于数列是环状的,不妨破环成链,令 。
结论: 能变换到 等价于对于任意 ,有 或 。
先证充分性。考虑将 变换至 的最后一次操作,若 则不用变换,否则必然是 且 。
由于此时 ,故有
从而 。
再证必要性。考虑每一轮变换 ,则 ,故我们必然可以让 进行一次变换,易知可以持续操作直至 。
所以只需要判断两种情况即可,时间复杂度 。
Code
#include <cstdio>
#include <cstring>
const int N = 4e5 + 5;
int a[N], b[N], n, T;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
b[i + n] = b[i];
}
bool flag = 1;
for (int i = 1; i <= n; i++) {
if (b[i] < a[i])
flag = 0;
}
if (!flag) {
puts("NO");
continue;
}
flag = 1;
for (int i = 1; i <= n; i++) {
if (b[i] > b[i + 1] + 1 && a[i] != b[i])
flag = 0;
}
puts(flag ? "YES" : "NO");
}
}
D
以下内容来源于题解
考虑对于每个人到根节点的路径,将每条边的胜负分别对应 ,得到一个长度为 的二进制数,可以证明这样的 个二进制数和树上 个叶节点一一对应,不妨设 表示叶节点 对应的二进制数。
我们考虑判断某个节点 是否可以通过不超过 调整使得 最终获胜,即每次在 中修改一位的值,最终能否使 全部为 ,不难发现这个问题等价于使得 中的 的个数不超过 ,显然,最终状态就是所有这样的 的最大值。
注意到所有 值中有 位为 的有 个,即答案为
时间复杂度 。
Code
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long int64;
const int N = 1e5 + 5;
const int64 mod = 1e9 + 7;
int64 fac[N], inv[N], n, k, ans;
inline int64 pow(int64 a, int64 b) {
int64 res = 1;
for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;
return res;
}
int64 binom(int64 x, int64 y) {
return 1LL * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int main() {
cin >> n >> k;
fac[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = pow(fac[i], mod - 2);
}
for (int i = 0; i <= min(n, k); i++) ans = (ans + binom(n, i)) % mod;
cout << ans << endl;
}
E
考虑枚举 ,此时有
令 ,则 为 的约数。
设 ,且 ,则 ,易知 ,从而满足要求的数对 的个数为 。
于是答案为
预处理 以内每个数的 值和所有约数,时间复杂度 。
Code
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int prime[N], vis[N], phi[N], n, cnt, ans;
inline void sieve() {
vis[1] = 1;
for (int i = 2; i < N; i++) {
if (vis[i] == 0) {
prime[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j]) {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
} else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
vector<int> f[N];
void factor() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i)
f[j].push_back(i);
}
}
int main() {
scanf("%d", &n);
sieve();
factor();
for (int c = 1; c <= n - 2; c++)
for (int d: f[n - c]) {
int lcm = 1LL * c * d / gcd(c, d) % mod;
ans = (ans + 1LL * lcm * phi[(n - c) / d] % mod) % mod;
}
printf("%d\n", ans);
}
F
待补。